package personal.leil.learning.quick;

import personal.leil.learning.utils.ArrayUtils;

/**
 * 快速排序
 * <p>
 * 快速排序代码实现
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-11
 */
public class QuickSort {

    /**
     * 算法实现
     * <p>
     * 递归的使用荷兰国旗解决快速排序的问题
     * </p>
     *
     * @param arr source array
     */
    public static void process(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序递归处理
     *
     * @param arr source array
     * @param L   left bound for process
     * @param R   right bound for process
     */
    public static void quickSort(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int randomIndex = L + (int) (Math.random() * (R - L + 1));
        ArrayUtils.swap(arr, randomIndex, R);
        int targetNum = arr[R];
        int l = L, i = L, r = R - 1;
        while (i <= r) {
            if (arr[i] < targetNum) {
                ArrayUtils.swap(arr, i++, l++);
            } else if (arr[i] > targetNum) {
                ArrayUtils.swap(arr, i, r--);
            } else {
                i++;
            }
        }
        /*
        经过上面的操作后，可以得到如下关系
        arr[l] >= targetNum
        arr[r] <= targetNum
        所以++r和R交换后，可知arr[r] = targetNum
        则后续递归应该在L~l-1和r+1~R两个范围展开
         */
        ArrayUtils.swap(arr, ++r, R);
        quickSort(arr, L, l - 1);
        quickSort(arr, r + 1, R);
    }


    /********************* For Test *************************/


    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArr(20);
        System.out.println("before sort:");
        ArrayUtils.printArr(arr);
        process(arr);
        System.out.println("after sort:");
        ArrayUtils.printArr(arr);
    }

}
